proof calculus

Definition

A proof system for a language $L$ is a polynomial time algorithm $V$ such that for all inputs $x$, $x \in L$ iff there exists a string $P$ such that $V$ accepts input $(x,P)$.

See also

• Hilbert calculus

References

1. https://mathweb.ucsd.edu/~sbuss/CourseWeb/Math268_2014W/Beame_IAS_proofcomplexity.pdf
2. https://mathweb.ucsd.edu/~sbuss/ResearchWeb/marktoberdorf97/paper.pdf